#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class allPossibleFullTree {
public:
    unordered_map<int, vector<TreeNode*> > ans;
    vector<TreeNode*> allPossibleFBT(int N) {
        if (!ans.count(N)) {
            // 当数字N对应的满二叉树不存在时，存储新的数据
            vector<TreeNode*> res;
            if (N % 2 == 0)
                // 偶数节点不存在满二叉树
                return res;
            if (N == 1)
                // 一个节点
                res.push_back(new TreeNode(0));
            else {
                // 奇数节点
                for (int i = 1; i <= N - 2; i += 2) {
                    // 遍历i: 1 - N-2，获取左右子树对应的可能的二叉树集合
                    vector<TreeNode*> leftVector = allPossibleFBT(i);
                    vector<TreeNode*> rightVector = allPossibleFBT(N - 1 - i);
                    // 对左右子树进行排列组合，获取对应的满二叉树组合
                    for (int j = 0; j < leftVector.size(); j++) {
                        for (int k = 0; k < rightVector.size(); k++) {
                            TreeNode* root = new TreeNode(0);
                            root->left = leftVector[j];
                            root->right = rightVector[k];
                            // 将组合加入res
                            res.push_back(root);
                        }
                    }
                }
            }
            // 将数字N对应的新结果加入ans
            ans[N] = res;
        }
        // 返回数字N对应的满二叉树集合
        return ans[N];
    }
};